#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10;
const int LL = N << 7;
const int inf = 0x7fffffff;
const int V = 1e9 + 7;

mt19937 rnd(19491001);

typedef long long ll;

int rt[N << 2];

namespace treap {
	int val[LL],ch[LL][2],siz[LL],pri[LL],ndn;
	int newnode(int x) { int y = ++ndn; val[y] = x; ch[y][0] = ch[y][1] = 0; siz[y] = 1; pri[y] = rnd() % V; return y;  }
	void pushup(int x) { siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1; }
	void split(int cur,int k,int &x,int &y) {
		if(cur == 0) return x = y = 0,void();
		if(val[cur] <= k) x = cur,split(ch[cur][1],k,ch[x][1],y),pushup(x);
		else y = cur,split(ch[cur][0],k,x,ch[y][0]),pushup(y);
	}
	int merge(int x,int y) {
		if(!x || !y) return x | y;
		if(pri[x] < pri[y]) return ch[x][1] = merge(ch[x][1],y),pushup(x),x;
		else return ch[y][0] = merge(x,ch[y][0]),pushup(y),y;
	}
	int kth(int x,int k) {
		while(true) {
			if(siz[ch[x][0]] + 1 == k) return x;
			if(k <= siz[ch[x][0]]) x = ch[x][0];
			else k -= siz[ch[x][0]] + 1, x = ch[x][1];
		}
	}
	int ans,a,b,c,d;
	void insert(int &rt,int x) { split(rt,x,a,b); rt = merge(merge(a,newnode(x)),b); }
	void del(int &rt,int x) { split(rt,x,a,b); split(a,x - 1,c,d); d = merge(ch[d][0],ch[d][1]); rt = merge(merge(c,d),b); }
	int rank(int &rt,int x) { split(rt,x - 1,a,b); ans = siz[a]; rt = merge(a,b); return ans; }
	int prev(int &rt,int x) { split(rt,x - 1,a,b); ans = siz[a] ? val[kth(a,siz[a])] : -inf; rt = merge(a,b); return ans; }
	int nxtv(int &rt,int x) { split(rt,x,a,b); ans = siz[b] ? val[kth(b,1)] : inf; rt = merge(a,b); return ans; }
}

using treap :: insert;
using treap :: del;
using treap :: prev;
using treap :: nxtv;

int a[N],Q,n;

void build(int o = 1,int l = 1,int r = n) {
	for(int i = l;i <= r;i++) insert(rt[o],a[i]);
	if(l == r) return; int mid = l + r >> 1;
	build(o << 1,l,mid); build(o << 1 | 1,mid + 1,r);
}

void seg_insert(int pos,int v,int o = 1,int l = 1,int r = n) {
	insert(rt[o],v); if(l == r) return; int mid = l + r >> 1;
	if(pos <= mid) seg_insert(pos,v,o << 1,l,mid); else seg_insert(pos,v,o << 1 | 1,mid + 1,r);
}

void seg_del(int pos,int v,int o = 1,int l = 1,int r = n) {
	del(rt[o],v); if(l == r) return; int mid = l + r >> 1;
	if(pos <= mid) seg_del(pos,v,o << 1,l,mid); else seg_del(pos,v,o << 1 | 1,mid + 1,r);
}

int seg_rank(int xl,int xr,int v,int o = 1,int l = 1,int r = n) {
	if(xl == l && xr == r) return treap :: rank(rt[o],v); int mid = l + r >> 1;
	if(xr <= mid) return seg_rank(xl,xr,v,o << 1,l,mid); else if(xl > mid) return seg_rank(xl,xr,v,o << 1 | 1,mid + 1,r);
	else return seg_rank(xl,mid,v,o << 1,l,mid) + seg_rank(mid + 1,xr,v,o << 1 | 1,mid + 1,r);
}

int seg_kth(int xl,int xr,int v) {
	int L = 0,R = 1e8;
	while(L <= R) {
        int mid = L + R >> 1;
        if(seg_rank(xl,xr,mid) + 1 <= v) L = mid + 1;
        else R = mid - 1;
	}
	return R;
}

int seg_prev(int xl,int xr,int v,int o = 1,int l = 1,int r = n) {
	if(xl == l && xr == r) return prev(rt[o],v); int mid = l + r >> 1;
	if(xr <= mid) return seg_prev(xl,xr,v,o << 1,l,mid); else if(xl > mid) return seg_prev(xl,xr,v,o << 1 | 1,mid + 1,r);
	else return max(seg_prev(xl,mid,v,o << 1,l,mid),seg_prev(mid + 1,xr,v,o << 1 | 1,mid + 1,r));
}

int seg_nxtv(int xl,int xr,int v,int o = 1,int l = 1,int r = n) {
	if(xl == l && xr == r) return nxtv(rt[o],v); int mid = l + r >> 1;
	if(xr <= mid) return seg_nxtv(xl,xr,v,o << 1,l,mid); else if(xl > mid) return seg_nxtv(xl,xr,v,o << 1 | 1,mid + 1,r);
	else return min(seg_nxtv(xl,mid,v,o << 1,l,mid),seg_nxtv(mid + 1,xr,v,o << 1 | 1,mid + 1,r));
}

int main() {
	scanf("%d %d",&n,&Q); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); build();
	while(Q--) {
		int op,l,r,k; scanf("%d",&op);
		if(op == 1) { scanf("%d %d %d",&l,&r,&k); printf("%d\n",seg_rank(l,r,k) + 1); }
		else if(op == 2) { scanf("%d %d %d",&l,&r,&k); printf("%d\n",seg_kth(l,r,k)); }
		else if(op == 3) { scanf("%d %d",&l,&r); seg_del(l,a[l]); a[l] = r; seg_insert(l,a[l]); }
		else if(op == 4) { scanf("%d %d %d",&l,&r,&k); printf("%d\n",seg_prev(l,r,k)); }
		else { scanf("%d %d %d",&l,&r,&k); printf("%d\n",seg_nxtv(l,r,k)); }
	} return 0;
}
